259. 3Sum Smaller
Medium

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

 

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2:

Input: nums = [], target = 0
Output: 0

Example 3:

Input: nums = [0], target = 0
Output: 0

 

Constraints:

  • n == nums.length
  • 0 <= n <= 3500
  • -100 <= nums[i] <= 100
  • -100 <= target <= 100
Accepted
88,891
Submissions
179,631
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.31 (52 votes)

Premium

Solution


Approach 1: Brute Force

Intuition

Find every possible set of triplets (i,j,k)(i, j, k) such that i<j<ki < j < k and test for the condition.

Complexity analysis

  • Time complexity: O(n3)O(n^3). The total number of such triplets is (n3)\binom{n}{3}, which is n!(n3)!×3!=n×(n1)×(n2)6\frac{n!}{(n - 3)! \times 3!} = \frac{n \times (n - 1) \times (n - 2)}{6}. Therefore, the time complexity of the brute force approach is O(n3)O(n^3).

  • Space complexity: O(1)O(1).


Intuition

Before we solve the threeSum problem, solve this simpler twoSum version:

Given a numsnums array, find the number of index pairs ii, jj with 0i<j<n0 \leq i < j < n that satisfy the condition nums[i]+nums[j]<targetnums[i] + nums[j] < target

If we sort the array first, then we can apply binary search to find the largest index jj such that nums[i]+nums[j]<targetnums[i] + nums[j] < target for each ii. Once we have found that largest index jj, we know there must be jij-i pairs that satisfy the above condition with ii's value fixed.

Finally, we can now apply the twoSum solution to threeSum directly by wrapping an outer for-loop around it.

Implementation

Note that in the above binary search we choose the upper middle element (left+right+12)(\frac{left+right+1}{2}) instead of the lower middle element (left+right2)(\frac{left+right}{2}). The reason is due to the terminating condition when there are two elements left. If we chose the lower middle element and the condition nums[mid]<targetnums[mid] < target evaluates to true, then the loop would never terminate. Choosing the upper middle element will guarantee termination.

Complexity analysis

  • Time complexity: O(n2logn)O(n^2 \log n). The binarySearch function takes O(logn)O(\log n) time, therefore the twoSumSmaller takes O(nlogn)O(n \log n) time. The threeSumSmaller wraps with another for-loop, and therefore is O(n2logn)O(n^2 \log n) time.

  • Space complexity: O(1)O(1) because no additional data structures are used.


Approach 3: Two Pointers

Intuition

Let us try sorting the array first. For example, nums=[3,5,2,8,1]nums = [3,5,2,8,1] becomes [1,2,3,5,8][1,2,3,5,8].

Let us look at an example nums=[1,2,3,5,8]nums = [1,2,3,5,8], and target=7target = 7.

[1, 2, 3, 5, 8]
 ↑           ↑
left       right

Let us initialize two indices, leftleft and rightright pointing to the first and last element respectively.

When we look at the sum of first and last element, it is 1+8=91 + 8 = 9, which is target\geq target. That tells us no index pair will ever contain the index rightright. So the next logical step is to move the right pointer one step to its left.

[1, 2, 3, 5, 8]
 ↑        ↑
left    right

Now the pair sum is 1+5=61 + 5 = 6, which is less than targettarget. How many pairs with one of the index=leftindex = left that satisfy the condition? You can tell by the difference between rightright and leftleft which is 33, namely (1,2),(1,3),(1,2), (1,3), and (1,5)(1,5). Therefore, we move leftleft one step to its right.

Implementation

Complexity analysis

  • Time complexity: O(n2)O(n^2). twoSumSmaller takes O(n)O(n) at most since it touches each element in the array once. It's parent function, threeSumSmaller takes O(nlogn)O(n\log n) to sort the array, then runs a loop that touches (n2)(n - 2) elements, invoking twoSumSmaller at each iteration. Therefore, the overall time complexity is O(nlogn+n2)O(n\log n + n^2), which boils down to O(n2)O(n^2).

  • Space complexity: O(1)O(1) because no additional data structures are used.

Report Article Issue

Comments: 26
sha256pki's avatar
Read More

Sorting array, rearranges the array, so not sure how is it solving original question of finding i,j,j in unsorted array.

82
Show 11 replies
Reply
Share
Report
sha256pki's avatar
Read More

Can I know why "right - left" is added to sum? I wonder how does it count distinct pairs of numbers between "left" and "right" that add upto less than target?

18
Show 6 replies
Reply
Share
Report
yehiahesham's avatar
Read More

is it me only, or the question was confusing about the i<j<k ? because most answers here are sorting the array which loses the positions to its values ! I mean if the problem wants any combination, it is poorly written !

25
Show 6 replies
Reply
Share
Report
2kvai777's avatar
Read More

Probably needs the condition i<j<k to be re-written as i != j != k.

To be honest I would have got it straight away if it was clearer

7
Reply
Share
Report
Chen_Xiang's avatar
Read More

I have a question for the twoSumSmaller:

private int twoSumSmaller(int[] nums, int startIndex, int target) {
    int sum = 0;
    for (int i = startIndex; i < nums.length - 1; i++) {
        int j = binarySearch(nums, i, target - nums[i]);
        sum += j - i;
    }
    return sum;
}

Why we use binary search for target - nums[i] from index i, rather than i+1? I think we need to find the right most position after i, then it is int j = binarySearch(nums, i+1, target - nums[i]);, but the answer is wrong. Thx!

7
Reply
Share
Report
RogerFederer's avatar
Read More

  def threeSumSmaller(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    result = 0
    nums.sort()
    for i in range(len(nums) - 2):
      l, r = i + 1, len(nums) - 1
      while l < r:
        s = nums[i] + nums[l] + nums[r]
        if s < target:
          result += r - l
          l += 1
        else:
          r -= 1
    return result

6
Show 3 replies
Reply
Share
Report
alexonezero's avatar
Read More

That

results += right-left;

is so tricky, i love it. Had to make myself a big comment block right on top of it lol

                // IMPORTANT
                // TRICKY PART HERE
                // IF THREESUM < TARGET, THEN BECAUSE THEE ARRAY IS SORTED
                // ALL NUMBERS IN BETWEEN WILL ALSO BE LESS OR EQUAL TO K
                // AND THEREFORE BE VALID ANSWERS

2
Reply
Share
Report
Nevsanev's avatar
Read More

Hi, I was wondering do we need to take care of overflow problem? I think target-nums[i] and nums[left] + nums[right] have a chance to cause overflow. Correct me if I am wrong

2
Show 2 replies
Reply
Share
Report
bowen17's avatar
Read More

For solution 3, space complexity, why is O(1), if we consider sorting, shouldn't be vary depends on the language (for example sort algorithm in python is O(n) but in Java is O(logn)). The space complexity solution I think should be consistent with solution 1 in # 15.

1
Reply
Share
Report
2amdrake's avatar
Read More

Why is it that some solutions that involve sorting say the space complexity is O(N) worst case auxiliary memory for the sort, some say O(logN), and some like these say O(1)? Are they just assuming a random sort method? what space complexity to give in an interview

1
Show 1 reply
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.